#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
#include<cmath>
using namespace std;

// 哈希表的节点（单链表）
template<class T>
struct hash_table_node
{
    T _val;
    hash_table_node* _next;

    hash_table_node(const T& x = T(), hash_table_node* next = nullptr)
        :_val(x)
        ,_next(next)
    {}
};

// 普通迭代器：封装node*
template<class T>
struct HashTable_iterator
{
    typedef hash_table_node<T> node;
    node* _pnode;               // 哈希表节点指针
    const vector<node*>* _ph;   // 哈希表指针
    size_t _pos;                // 该节点在哈希表的位置

    HashTable_iterator(node* pn = nullptr, const vector<node*>* ph = nullptr, size_t pos = 0)
        :_pnode(pn)
        ,_ph(ph)
        ,_pos(pos)
    {}

    typedef HashTable_iterator Self;
    // 前置++
    Self& operator++()
    {
        assert(_pnode);
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else{
            _pos++;
            while(_pos < _ph->size() && !(*_ph)[_pos])
                _pos++;
            if(_pos < _ph->size())
                _pnode = (*_ph)[_pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    // 后置++
    Self operator++(int)
    {
        Self tmp(*this);
        ++(*this);
        return tmp;
    }

    T& operator*() { return _pnode->_val; }
    T* operator->() { return &_pnode->_val; }
    bool operator!= (const Self& it) const
    { return _pnode != it._pnode; }
    bool operator== (const Self& it) const
    { return _pnode == it._pnode; }
};

// const迭代器：封装const node*
template<class T>
struct HashTable_const_iterator
{
    typedef hash_table_node<T> node;
    const node* _pnode;       // 哈希表节点指针
    const vector<node*>* _ph; // 哈希表指针
    size_t _pos;              // 该节点在哈希表的位置

    HashTable_const_iterator(const node* pn = nullptr, const vector<node*>* ph = nullptr, size_t pos = 0)
        :_pnode(pn)
        ,_ph(ph)
        ,_pos(pos)
    {}

    // 可能会用普通迭代器构造constdiedaiq
    HashTable_const_iterator(const HashTable_iterator<T>& it)
        :_pnode(it._pnode)
        ,_ph(it._ph)
        ,_pos(it._pos)
    {}

    typedef HashTable_const_iterator Self;
    // 前置++
    Self& operator++()
    {
        assert(_pnode);
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else{
            _pos++;
            while(_pos < _ph->size() && !(*_ph)[_pos])
                _pos++;
            if(_pos < _ph->size())
                _pnode = (*_ph)[_pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    // 后置++
    Self operator++(int)
    {
        Self tmp(*this);
        ++(*this);
        return tmp;
    }
    const T& operator*() { return _pnode->_val; }
    const T* operator->() { return &_pnode->_val; }
    bool operator!= (const Self& it) const
    { return _pnode != it._pnode; }
    bool operator== (const Self& it) const
    { return _pnode == it._pnode; }
};

// 将元素x处理成非负整数
template<class T>
struct HashFunc
{
    size_t operator() (const T& x) const
    {
        return (size_t)x;
    }
};

// 特化string版本
template<>
struct HashFunc<string>
{
    size_t operator() (const string& x) const
    {
    	// 把string类型看作131进制的数（有相关研究表明，这样哈希冲突较少）
    	// 例如x = "abc"
    	// 则其key = 'a'*131^2 + 'b'*131^1 + 'c'*131^0
        size_t res = 0;
        for(auto& c : x)
            res = res * 131 + c;
        return res;
    }
};

// 哈希表
template<class K,		    // 元素的关键字key的类型
		 class T,		    // 实际存储的元素类型
		 class ExtractKey,	// 提取元素的关键字
		 class Hash>	    // 将key处理成非负整数
class HashTable
{
    typedef hash_table_node<T> node;
    vector<node*> _h;   // 链表数组
    size_t _size = 0;   // 表中的元素个数
    
    // 提取元素的 key
    const K& get_key(const T& x) const
    {
        static ExtractKey f;
        return f(x);
    }
    // 将key转化成非负整数（计算key的哈希值）
    size_t get_hash(const K& key) const
    {
        static Hash f;
        return f(key);
    }
    // 找 >= n的最小质数
    size_t get_next_prime(size_t n)
    {
        static size_t p[29] =
        {   17,
            53,         97,         193,       389,       769,
            1543,       3079,       6151,      12289,     24593,
            49157,      98317,      196613,    393241,    786433,
            1572869,    3145739,    6291469,   12582917,  25165843,
            50331653,   100663319,  201326611, 402653189, 805306457, 
            1610612741, 3221225473, 4294967291
        };
        if(n > p[28]) return p[28];
        return *lower_bound(p, p + 29, n);
    }

public:
    typedef HashTable_iterator<T> iterator;
    typedef HashTable_const_iterator<T> const_iterator;
    iterator begin()
    {
        if(!_size) return end();   
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return iterator(_h[i], &_h, i);
        return end();   // 按理说不会走到这里，但有些编译器会强制要求有返回值
    }
    iterator end() 
    { 
        return iterator(nullptr, &_h, -1); 
        //注意不要写成：{nullptr, &_h, -1}; C++11开始，对列表初始化，禁止窄化转换（有符号负数→无符号）
    }

    const_iterator begin() const
    {
        if(!_size) return end();
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return const_iterator(_h[i], &_h, i);
        return end();
    }
    const_iterator end() const 
    { 
        return const_iterator(nullptr, &_h, 0); 
    }

    HashTable(int n = 17)
        :_h(get_next_prime(n))		// 初始时，表长设为17
    {}
    
    // 列表构造
    HashTable(initializer_list<T> il)
    {
        reserve(ceil(il.size() / 0.7)); // 尽量不要超过负载因子. ceil是向上取整
        for(const auto& e : il)
            insert(e);
    }

    // 析构
    ~HashTable() { clear(); }
    void clear()
    {
        for(const node* i : _h)
            while(i)
            {
                node* next = i->_next;
                delete i;
                i = next;
            }
        _size = 0;
    }

    // 拷贝构造
    HashTable(const HashTable& ht)
    {
        _h.resize(ht._h.size());
        for(auto& e : ht)
            insert(e);
    }

    void swap(HashTable& ht)
    {
        _h.swap(ht._h);
        std::swap(_size, ht._size);
    }

    // 赋值重载
    HashTable& operator= (const HashTable& ht)
    {
        if(this != &ht)
        {
            HashTable tmp(ht);
            swap(tmp);
        }
        return *this;
    }

    size_t size() const { return  _size; }
    bool empty() const { return !_size; }

    // find的参数应当是K类型。找到了关键字为key的迭代器，否则返回end()
    iterator find(const K& key)
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();	
        for(node* i = _h[pos]; i; i = i->_next)
            if(get_key(i->_val) == key) // 提取_val的key再进行比较
                return iterator(i, &_h, pos);
        return end(); // 未找到返回空
    }

    // 顺便提供const版本的find
    const_iterator find(const K& key) const
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();	
        for(const node* i = _h[pos]; i; i = i->_next)
            if(get_key(i->_val) == key) // 提取_val的key再进行比较
                return const_iterator(i, &_h, pos);
        return end(); // 未找到返回空
    }

    // insert的参数应当是T类型。成功插入返回：<值为x的迭代器, true>; 否则返回<值为x的迭代器, false>
    pair<iterator, bool> insert(const T& x)
    {
        iterator it = find(get_key(x));
        if(it != end()) return {it, false};

        if(_size >= 0.7 * _h.size())
            reserve(_h.size() + 1);

        // 先提取val的key，然后转化成非负整数，再找到其存储的下标
        int pos = get_hash(get_key(x)) % _h.size();
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return {iterator(cur, &_h, pos), true};
    }

    // 让新容量变为 >= n的最小质数
    void reserve(size_t n)
    {
        if(_h.size() >= n) return;

        n = get_next_prime(n); // 找 >= n的最小质数
        vector<node*> new_h(n);
        for(int i = 0; i < _h.size(); i++)
        {
            if(_h[i])
            {
                // 为了提高效率，直接把原哈希表的节点移动到新表中
                node* j = _h[i];
                while(j)
                {
                    // 先提取j->_val的key，然后转化成非负整数，再找到其存储的下标
                    int pos = get_hash(get_key(j->_val)) % new_h.size();
                    node* next = j->_next;
                    j->_next = new_h[pos];
                    new_h[pos] = j;
                    j = next;
                }
            }
        }
        _h.swap(new_h);
    }


    // erase的参数应当也是K类型
    bool erase(const K& key)
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();
        for(node* i = _h[pos], *pre = nullptr; i; pre = i, i = i->_next)
        {
            if(get_key(i->_val) == key)
            {
                if(!pre)    // 这里说明被删除的元素是头节点
                    _h[pos] = _h[pos]->_next;
                else
                    pre->_next = i->_next;
                delete i;
                _size--;
                return true;
            }
        }
        return false;
    }
};

